#include "../tools.h"

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int size = 0;
        ListNode *p = head;
        while(p != nullptr) { ++size; p = p->next;}

        ListNode *h1, *e1, *h2, *e2;
        ListNode *left, *right;
        ListNode headpre(-1, head);
        int interval = 1, len1, len2;
        while(interval < size){
            // 每轮都从开头开始
            left = &headpre, right = headpre.next; // left 用于合并
            while(right != nullptr){
                // [h, e)
                h1 = right;
                for(len1 = 0; len1 < interval && right != nullptr; ++len1) right = right->next;
                if(len1 < interval) continue;
                e1 = right;

                h2 = right;
                for(len2 = 0; len2 < interval && right != nullptr; ++len2) right = right->next;
                e2 = right;

                // 合并 - left 晚 h 一步
                while(h1 != e1 && h2 != e2){
                    if(h1->val < h2->val) {left->next = h1; h1 = h1->next;}
                    else {left->next = h2; h2 = h2->next;}
                    left = left->next;
                }
                if(h1 != e1){
                    left->next = h1;
                    while(left->next != e1) left = left->next; // 用 left->next !!!
                    // left->next = right; // 其实放到这即可
                }
                if(h2 != e2){
                    left->next = h2;
                    while(left->next != e2) left = left->next;
                }
                left->next = right; // !!!
            }
            interval *= 2;
        }
        return headpre.next;
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;
    
    vector<int> data = {4,2,1,3};
    ListNode* head = create_list(data);
    show(head);

    ListNode* p = sol.sortList(head);
    show(p);


    return 0;
}